package com.hao.sort;

/**
 * TODO
 * 堆排序
 * @author 97472
 * @version 1.0
 * @date 2021/5/27 15:56
 */
public class HeapSort {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{4,6,8,5,9};
        heapSort(arr);
        for (Integer i:arr) {
            System.out.print("  "+i);
        }
    }
    public static void heapSort(Integer[] arr){
        // 1. 首先将整个树变成大顶堆,我们从下到上，从右至左将所有的飞叶子节点进行堆积。
        // i = arr.length/2 - 1 这个节点是最右边的非叶子节点。依次递减就能便利所有的飞叶子节点
        for (int i = arr.length/2 - 1; i >= 0; i--) {
            heapify(arr,i, arr.length);
        }

        // 2. 将根节点的值与数组的未排序的最后一个位置的元素进行交换
        // 3. 再对根进行重新堆积
        // 4. 重复3-4
        for (int i = arr.length - 1; i >= 0; i--) {
            // 交换
            Integer temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            heapify(arr,0,i);
        }
    }
    /**
     * 将某个树变成大顶堆
     * @param arr 存储数据的数组
     * @param i 非子叶节点在数组中的索引
     * @param length 数组中需要处理的数据的长度。
     */
    private static void heapify(Integer[] arr, Integer i, Integer length){
        // 移位法需要 当前节点的值
        Integer temp = arr[i];
        // j=i*2+1 表示i节点的左子节点 j = j*2+1表示位当前节点的下一个左子节点
        for (int j = i*2+1; j < length; j = j*2+1) {
            // 将i节点的左子节点与右子节点比较，将索引j指向二者中的最大值。
            // 为什么要判断这个？因为大顶堆的非叶子节点要比子节点大，那么如果比子节点中最大的比较，如果大就无需操作，小的话也只要跟最大值交换。
            if (j+1 < length && arr[j] < arr[j+1]){
                j++;
            }
            // 判断子节点中最大值是否大于节点i
            // 如果大于就将该字节移至i
            // 如果小于就直接跳出循环，因为默认是的是下面的节点已经成顶堆了，（只有上面出现改变，下面才需要重新调整）

            // 交换法
            /*
                if (arr[j] > arr[i]){
                Integer temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                // 记录进行下一轮比较的时候，就是以j节点进行判断
                i = j;
            }else {
                break;
            }*/
            // 移位法
            if (arr[j] > temp){
                arr[i] = arr[j];
                // 记录temp所在的位置。
                i = j;
            }else {
                break;
            }
        }
        // 移位法需要
        arr[i] = temp;
    }
}
